home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / os2 / adaptor.zip / ADAPT.ZIP / adaptor / src / sets.c < prev    next >
C/C++ Source or Header  |  1993-03-22  |  11KB  |  446 lines
  1. /* $Id: Sets.c,v 1.10 1992/05/05 13:19:05 grosch rel $ */
  2.  
  3. /* $Log: Sets.c,v $
  4.  * Revision 1.10  1992/05/05  13:19:05  grosch
  5.  * added rcsid
  6.  *
  7.  * Revision 1.9  1992/03/30  09:53:37  grosch
  8.  * fixed bug in IsSubset: removed operator !
  9.  *
  10.  * Revision 1.8  1992/02/06  09:29:54  grosch
  11.  * fixed bug: stdio and ANSI C
  12.  *
  13.  * Revision 1.7  1992/01/31  16:31:44  grosch
  14.  * adaption to ANSI C
  15.  *
  16.  * Revision 1.6  1991/11/21  14:28:16  grosch
  17.  * new version of RCS on SPARC
  18.  *
  19.  * Revision 1.5  91/07/17  17:23:36  grosch
  20.  * introduced ARGS trick for ANSI compatibility
  21.  * 
  22.  * Revision 1.4  90/09/20  09:12:25  grosch
  23.  * calmed down lint
  24.  * 
  25.  * Revision 1.3  90/07/04  14:34:02  grosch
  26.  * introduced conditional include
  27.  * 
  28.  * Revision 1.2  89/12/08  17:25:01  grosch
  29.  * complete redesign in order to increase efficiency
  30.  * 
  31.  * Revision 1.1  89/01/09  17:29:23  grosch
  32.  * added functions Size, Minimum, and Maximum
  33.  * 
  34.  * Revision 1.0  88/10/04  11:44:44  grosch
  35.  * Initial revision
  36.  * 
  37.  */
  38.  
  39. /* Ich, Doktor Josef Grosch, Informatiker, Sept. 1987 */
  40.  
  41. static char rcsid [] = "$Id: Sets.c,v 1.10 1992/05/05 13:19:05 grosch rel $";
  42.  
  43. # include "ratc.h"
  44. # include "Sets.h"
  45. # include "DynArray.h"
  46. # include "General.h"
  47.  
  48. # define BitsPerByte        8
  49. # define BytesPerBitset        BitsPerBitset / BitsPerByte
  50. # define ONE            0x80000000
  51. # define NoCard            -1
  52.  
  53. # ifdef PCS10
  54. # define CALL(f)    (* f)
  55. # else
  56. # define CALL(f)    f
  57. # endif
  58.  
  59. void MakeSet
  60. # ifdef __STDC__
  61.    (tSet * Set, cardinal MaxSize)
  62. # else
  63.    (Set, MaxSize)
  64.    tSet *    Set    ;
  65.    cardinal    MaxSize    ;
  66. # endif
  67.    {
  68.       unsigned long    ElmtCount    ;
  69.  
  70.       ElmtCount = (MaxSize + BitsPerBitset - (MaxSize & MaskBitsPerBitset)) >> LdBitsPerBitset;
  71.       MakeArray ((char * *) & Set->BitsetPtr, & ElmtCount, (unsigned long) BytesPerBitset);
  72.       Set->MaxElmt = MaxSize;
  73.       Set->LastBitset = ElmtCount - 1;
  74.       AssignEmpty (Set);
  75.    }
  76.       
  77. void ReleaseSet (Set)
  78.    tSet *    Set;
  79.    {
  80.       unsigned long    ElmtCount    ;
  81.  
  82.       ElmtCount = Set->LastBitset + 1;
  83.       ReleaseArray ((char * *) & Set->BitsetPtr, & ElmtCount, (unsigned long) BytesPerBitset);
  84.    }
  85.  
  86. void Union (Set1, Set2)
  87.    tSet *    Set1    ;
  88.    tSet *    Set2    ;
  89.    {
  90.       register tSet *    rSet1    = Set1;
  91.       register cardinal    i     = rSet1->LastBitset + 1;
  92.       register BITSET *    s1    = rSet1->BitsetPtr;
  93.       register BITSET *    s2    = Set2->BitsetPtr;
  94.       register tSet *    rSet2    = Set2;
  95.  
  96.       do {* s1 ++ |= * s2 ++;} while (-- i);
  97.       rSet1->Card      = NoCard;
  98.       rSet1->FirstElmt = Min (rSet1->FirstElmt, rSet2->FirstElmt);
  99.       rSet1->LastElmt  = Max (rSet1->LastElmt , rSet2->LastElmt );
  100.    }
  101.  
  102. void Difference (Set1, Set2)
  103.    tSet *    Set1    ;
  104.    tSet *    Set2    ;
  105.    {
  106.       register tSet *    rSet1    = Set1;
  107.       register cardinal    i     = rSet1->LastBitset + 1;
  108.       register BITSET *    s1    = rSet1->BitsetPtr;
  109.       register BITSET *    s2    = Set2->BitsetPtr;
  110.  
  111.       do {* s1 ++ &= ~ * s2 ++;} while (-- i);
  112.       rSet1->Card = NoCard;
  113.    }
  114.  
  115. void Intersection (Set1, Set2)
  116.    tSet *    Set1    ;
  117.    tSet *    Set2    ;
  118.    {
  119.       register tSet *    rSet1    = Set1;
  120.       register cardinal    i     = rSet1->LastBitset + 1;
  121.       register BITSET *    s1    = rSet1->BitsetPtr;
  122.       register BITSET *    s2    = Set2->BitsetPtr;
  123.       register tSet *    rSet2    = Set2;
  124.  
  125.       do {* s1 ++ &= * s2 ++;} while (-- i);
  126.       rSet1->Card      = NoCard;
  127.       rSet1->FirstElmt = Max (rSet1->FirstElmt, rSet2->FirstElmt);
  128.       rSet1->LastElmt  = Min (rSet1->LastElmt , rSet2->LastElmt);
  129.    }
  130.  
  131. void SymDiff (Set1, Set2)
  132.    tSet *    Set1    ;
  133.    tSet *    Set2    ;
  134.    {
  135.       register tSet *    rSet1    = Set1;
  136.       register cardinal    i     = rSet1->LastBitset + 1;
  137.       register BITSET *    s1    = rSet1->BitsetPtr;
  138.       register BITSET *    s2    = Set2->BitsetPtr;
  139.       register tSet *    rSet2    = Set2;
  140.  
  141.       do {* s1 ++ ^= * s2 ++;} while (-- i);
  142.       rSet1->Card      = NoCard;
  143.       rSet1->FirstElmt = Min (rSet1->FirstElmt, rSet2->FirstElmt);
  144.       rSet1->LastElmt  = Max (rSet1->LastElmt , rSet2->LastElmt);
  145.    }
  146.  
  147. void Complement (Set)
  148.    tSet *    Set    ;
  149.    {
  150.       register tSet *    rSet    = Set;
  151.       register cardinal    i     = rSet->LastBitset;
  152.       register BITSET *    s1    = rSet->BitsetPtr;
  153.  
  154.       while (i --) {* s1 = ~ * s1; s1 ++;}
  155.       * s1 = ((long) ONE >> (rSet->MaxElmt & MaskBitsPerBitset)) & ~ * s1;
  156.       if (rSet->Card != NoCard) rSet->Card = (short) rSet->MaxElmt + 1 - rSet->Card;
  157.       rSet->FirstElmt = 0;
  158.       rSet->LastElmt  = rSet->MaxElmt;
  159.    }
  160.  
  161. void Include
  162. # ifdef __STDC__
  163.    (tSet * Set, cardinal Elmt)
  164. # else
  165.    (Set, Elmt)
  166.    tSet *    Set    ;
  167.    cardinal    Elmt    ;
  168. # endif
  169.    {
  170.       register tSet *    rSet    = Set;
  171.       register cardinal    rElmt    = Elmt;
  172.  
  173.       rSet->BitsetPtr [rElmt >> LdBitsPerBitset] |= (unsigned long) ONE >> (rElmt & MaskBitsPerBitset);
  174.       rSet->Card      = NoCard;
  175.       rSet->FirstElmt = Min (rSet->FirstElmt, rElmt);
  176.       rSet->LastElmt  = Max (rSet->LastElmt , rElmt);
  177.    }
  178.  
  179. void Exclude
  180. # ifdef __STDC__
  181.    (tSet * Set, cardinal Elmt)
  182. # else
  183.    (Set, Elmt)
  184.    tSet *    Set    ;
  185.    cardinal    Elmt    ;
  186. # endif
  187.    {
  188.       register tSet *    rSet    = Set;
  189.       register cardinal    rElmt    = Elmt;
  190.  
  191.       rSet->BitsetPtr [rElmt >> LdBitsPerBitset] &= ~ ((unsigned long) ONE >> (rElmt & MaskBitsPerBitset));
  192.       rSet->Card = NoCard;
  193.       if (rElmt == rSet->FirstElmt && rElmt < rSet->MaxElmt) rSet->FirstElmt ++;
  194.       if (rElmt == rSet->LastElmt && rElmt > 0) rSet->LastElmt --;
  195.    }
  196.  
  197. cardinal Card (Set)
  198.    tSet *    Set    ;
  199.    {
  200.       register tSet * rSet = Set;
  201.  
  202.       if (rSet->Card == NoCard) {
  203.      register cardinal i, n;
  204.      register cardinal last = rSet->LastElmt;
  205.  
  206.      n = 0;
  207.      for (i = rSet->FirstElmt; i <= last; i ++) {
  208.         if (IsElement (i, rSet)) n ++;
  209.      }
  210.      rSet->Card = n;
  211.       }
  212.       return rSet->Card;
  213.    }
  214.     
  215. cardinal Minimum (Set)
  216.    tSet *    Set    ;
  217.    {
  218.       register tSet *    rSet    = Set;
  219.       register cardinal    i;
  220.       register cardinal    last    = rSet->LastElmt;
  221.  
  222.       for (i = rSet->FirstElmt; i <= last; i ++) {
  223.      if (IsElement (i, rSet)) {
  224.         rSet->FirstElmt = i;
  225.         return i;
  226.      }
  227.       }
  228.       return 0;
  229.    }
  230.     
  231. cardinal Maximum (Set)
  232.    tSet *    Set    ;
  233.    {
  234.       register tSet *    rSet    = Set;
  235.       register cardinal    i;
  236.       register cardinal    first    = rSet->FirstElmt;
  237.  
  238.       for (i = rSet->LastElmt; i >= first; i --) {
  239.      if (IsElement (i, rSet)) {
  240.         rSet->LastElmt = i;
  241.         return i;
  242.      }
  243.       }
  244.       return 0;
  245.    }
  246.     
  247. cardinal Extract (Set)
  248.    tSet *    Set    ;
  249.    {
  250.       register cardinal i = Minimum (Set);
  251.       Exclude (Set, i);
  252.       return i;
  253.    }
  254.  
  255. bool IsSubset (Set1, Set2)
  256.    tSet *    Set1    ;
  257.    tSet *    Set2    ;
  258.    {
  259.       register tSet *    rSet1    = Set1;
  260.       register cardinal    i     = rSet1->LastBitset + 1;
  261.       register BITSET *    s1    = rSet1->BitsetPtr;
  262.       register BITSET *    s2    = Set2->BitsetPtr;
  263.  
  264.       do {
  265.      if (* s1 ++ & ~ * s2 ++) return false;
  266.       } while (-- i);
  267.       return true;
  268.    }
  269.  
  270. bool IsEqual (Set1, Set2)
  271.    tSet *    Set1    ;
  272.    tSet *    Set2    ;
  273.    {
  274.       register tSet *    rSet1    = Set1;
  275.       register cardinal    i     = rSet1->LastBitset + 1;
  276.       register BITSET *    s1    = rSet1->BitsetPtr;
  277.       register BITSET *    s2    = Set2->BitsetPtr;
  278.  
  279.       do {
  280.      if (* s1 ++ != * s2 ++) return false;
  281.       } while (-- i);
  282.       return true;
  283.    }
  284.     
  285. bool IsEmpty (Set)
  286.    tSet *    Set    ;
  287.    {
  288.       register tSet * rSet = Set;
  289.  
  290.       if (rSet->FirstElmt <= rSet->LastElmt) {
  291.      register cardinal i  = rSet->LastBitset + 1;
  292.      register BITSET * s1 = rSet->BitsetPtr;
  293.  
  294.      do {
  295.         if (* s1 ++ != 0) return false;
  296.      } while (-- i);
  297.       }
  298.       return true;
  299.    }
  300.     
  301. bool Forall (Set, Proc)
  302.    tSet *    Set    ;
  303.    bool        (* Proc) ();
  304.    {
  305.       register tSet *    rSet    = Set;
  306.       register cardinal    i;
  307.       register cardinal    last    = rSet->LastElmt;
  308.  
  309.       for (i = rSet->FirstElmt; i <= last; i ++) {
  310.      if (IsElement (i, rSet) && ! CALL(Proc) (i)) return false;
  311.       }
  312.       return true;
  313.    }
  314.     
  315. bool Exists (Set, Proc)
  316.    tSet *    Set    ;
  317.    bool        (* Proc) ();
  318.    {
  319.       register tSet *    rSet    = Set;
  320.       register cardinal    i;
  321.       register cardinal    last    = rSet->LastElmt;
  322.  
  323.       for (i = rSet->FirstElmt; i <= last; i ++) {
  324.      if (IsElement (i, rSet) && CALL(Proc) (i)) return true;
  325.       }
  326.       return false;
  327.    }
  328.     
  329. bool Exists1 (Set, Proc)
  330.    tSet *    Set    ;
  331.    bool        (* Proc) ();
  332.    {
  333.       register tSet *    rSet    = Set;
  334.       register cardinal    i, n;
  335.       register cardinal    last    = rSet->LastElmt;
  336.  
  337.       n = 0;
  338.       for (i = rSet->FirstElmt; i <= last; i ++) {
  339.      if (IsElement (i, rSet) && CALL(Proc) (i)) n ++;
  340.       }
  341.       return n == 1;
  342.    }
  343.  
  344. void Assign (Set1, Set2)
  345.    tSet *    Set1    ;
  346.    tSet *    Set2    ;
  347.    {
  348.       register tSet *    rSet1    = Set1;
  349.       register cardinal    i     = rSet1->LastBitset + 1;
  350.       register BITSET *    s1    = rSet1->BitsetPtr;
  351.       register BITSET *    s2    = Set2->BitsetPtr;
  352.       register tSet *    rSet2    = Set2;
  353.  
  354.       do {* s1 ++ = * s2 ++;} while (-- i);
  355.       rSet1->Card      = rSet2->Card;
  356.       rSet1->FirstElmt = rSet2->FirstElmt;
  357.       rSet1->LastElmt  = rSet2->LastElmt;
  358.    }
  359.  
  360. void AssignElmt
  361. # ifdef __STDC__
  362.    (tSet * Set, cardinal Elmt)
  363. # else
  364.    (Set, Elmt)
  365.    tSet *    Set    ;
  366.    cardinal    Elmt    ;
  367. # endif
  368.    {
  369.       register tSet *    rSet    = Set;
  370.       register cardinal    rElmt    = Elmt;
  371.  
  372.       AssignEmpty (rSet);
  373.       Include (rSet, rElmt);
  374.       rSet->Card      = 1;
  375.       rSet->FirstElmt = rElmt;
  376.       rSet->LastElmt  = rElmt;
  377.    }
  378.  
  379. void AssignEmpty (Set)
  380.    tSet *    Set    ;
  381.    {
  382.       register tSet *    rSet    = Set;
  383.       register cardinal    i     = rSet->LastBitset + 1;
  384.       register BITSET *    s1    = rSet->BitsetPtr;
  385.  
  386.       do {* s1 ++ = 0;} while (-- i);
  387.       rSet->Card      = 0;
  388.       rSet->FirstElmt = rSet->MaxElmt;
  389.       rSet->LastElmt  = 0;
  390.    }
  391.  
  392. void ForallDo (Set, Proc)
  393.    tSet *    Set    ;
  394.    void        (* Proc) ();
  395.    {
  396.       register tSet *    rSet    = Set;
  397.       register cardinal    i;
  398.       register cardinal    last    = rSet->LastElmt;
  399.  
  400.       for (i = rSet->FirstElmt; i <= last; i ++) {
  401.      if (IsElement (i, rSet)) CALL(Proc) (i);
  402.       }
  403.    }
  404.  
  405. void ReadSet (File, Set)
  406.    FILE *    File    ;
  407.    tSet *    Set    ;
  408.    {
  409.       register tSet * rSet = Set;
  410.       int i, card = 0;
  411.  
  412.       while (fgetc (File) != '{');
  413.       AssignEmpty (rSet);
  414.       for (;;) {
  415.      if (fgetc (File) == '}') break;
  416.      (void) fscanf (File, "%d", & i);
  417.      Include (rSet, i);
  418.      card ++;
  419.       }
  420.       rSet->Card = card;
  421.    }
  422.  
  423. static FILE * g;
  424.  
  425. void PrintElmt (Elmt)
  426.    cardinal    Elmt    ;
  427.    {
  428.       (void) fprintf (g, " %d", Elmt);
  429.    }
  430.  
  431. void WriteSet (File, Set)
  432.    FILE *    File    ;
  433.    tSet *    Set    ;
  434.    {
  435.       g = File;
  436.       (void) fprintf (File, "{");
  437.       ForallDo (Set, PrintElmt);
  438.       (void) fprintf (File, "}");
  439.    }
  440.  
  441. void InitSets ()
  442.    {
  443.       if (sizeof (BITSET) != BytesPerBitset)
  444.      (void) fprintf (stderr, "Sets: sizeof (BITSET) = %d\n", sizeof (BITSET));
  445.    }
  446.